/**
 * //Given n non-negative integers representing an elevation map where the width
 * //of each bar is 1, compute how much water it can trap after raining.
 * //
 * //
 * // Example 1:
 * //
 * //
 * //Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
 * //Output: 6
 * //Explanation: The above elevation map (black section) is represented by array [
 * //0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section)
 * //are being trapped.
 * //
 * //
 * // Example 2:
 * //
 * //
 * //Input: height = [4,2,0,3,2,5]
 * //Output: 9
 * //
 * //
 * //
 * // Constraints:
 * //
 * //
 * // n == height.length
 * // 1 <= n <= 2 * 10⁴
 * // 0 <= height[i] <= 10⁵
 * //
 * //
 * // Related Topics 栈 数组 双指针 动态规划 单调栈 👍 3885 👎 0
 */

package com.xixi.dataStructure.stack;

import java.util.Stack;

public class ID00042TrappingRainWater {
    public static void main(String[] args) {

        Solution solution = new ID00042TrappingRainWater().new Solution();
        solution.trap(new int[]{0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1});
    }


    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int trap(int[] height) {

            int res = 0;
            int n = height.length;
            if (height.length < 3) return res;
            //单调栈，左侧高于右侧。
            Stack<Integer> indexStack = new Stack<>();
            int current = 0;
            while (current < n) {

                //遇到右侧遇到高墙，出栈计算该 行 水量
                while (!indexStack.isEmpty() && height[current] > height[indexStack.peek()]) { //
                    int h = height[indexStack.pop()];//计算高度
                    if (indexStack.isEmpty()) break; //最左侧是leftMax，不计算
                    int distance = current - indexStack.peek() - 1; //当前墙和 i-1的墙的距离
                    int min = Math.min(height[indexStack.peek()], height[current]);
                    res += distance * (min - h);
                }
                indexStack.push(current);
                current++;

            }

            return res;

        }
    }
//leetcode submit region end(Prohibit modification and deletion)


}